package com.yahoo.labs.snow.solver;

import it.unimi.dsi.fastutil.ints.IntOpenHashSet;

import java.util.Vector;

import com.yahoo.labs.snow.ProblemInstance;
import com.yahoo.labs.snow.Snowflake;

/**
 * Create snowflakes by adding elements sequentially in a random order, creating a new snowflake if violating a constraint.
 * 
 * @author chato
 *
 */
public class SequentialScanSolver extends Solver {
	
	public SequentialScanSolver(ProblemInstance problem) {
		super(problem);
	}

	@Override
	public Vector<Snowflake> solve(int numSnowflakes) {
		Vector<Snowflake> solution = new Vector<Snowflake>();
		IntOpenHashSet nodes = new IntOpenHashSet(problem.getIds());
		IntOpenHashSet currentSnowflake = new IntOpenHashSet();
		
		while( ! nodes.isEmpty() ) {
			boolean added = false;
			for( int node: nodes ) {
				if( checkBudgetAndCoverageConstraint( currentSnowflake, node ) ) {
					currentSnowflake.add(node);
					nodes.remove(node);
					added = true;
					break;
				}
			}
			
			if( ! added ) {
				solution.add(new Snowflake(currentSnowflake, problem));
				currentSnowflake.clear();
				if( solution.size() == numSnowflakes ) {
					return solution;
				}
			}
		}
		if( (solution.size() < numSnowflakes) && (! currentSnowflake.isEmpty()) ) {
			solution.add(new Snowflake(currentSnowflake, problem));
		}
		return solution;
	}

	public int pickRandom(IntOpenHashSet set) {
		int[] elements = set.toArray(new int[] {});
		int position = (int) Math.floor(Math.random() * elements.length);
		return elements[position];
	}
}
